package com.heima.algorithm.sort;

import java.util.concurrent.ThreadLocalRandom;

/**
 * <strong>单边循环快速排序（lomuto洛穆托分区方案）</strong>
 * <p>每轮找到一个基准点元素，把比它小的放在左边，把比它大的放在右边，这称为分区</p>
 * <ul>
 *     罗穆托分区方案：
 *     <li>选择最右元素作为基准点元素</li>
 *     <li>i和j都从索引0开始</li>
 *     <li>j指针负责找到比基准点小的元素</li>
 *     <li>i指针负责找到比基准点大或等的元素</li>
 *     <li>i指针找打比基准点大的元素的时候如果j没有找到比基准点小的，那么i应当停下来，等待i找到</li>
 *     <li>当i和j都找到了，那么交换i和j索引处元素的值</li>
 *     <li>如果i和j指向的同一个元素，如果j满足条件，i不满足，都自增一；j不满足，i满足，那么i不动，j自增一</li>
 *     <li>这样i最后的位置就是大于等于基准点元素的第一个元素</li>
 *     <li>最后基准点与i交换，i即为分区位置</li>
 * </ul>
 * @author 勾新杰
 * @version 1.0
 * @date 2024/10/1 10:11
 */
public class QuickSortLomuto {
    //（1）基于比较的排序算法
    //（2）最好情况：O(NlogN)，最坏情况：O(N^2)，平均情况：O(NlogN)，空间复杂度：O(logN)，稳定：否，思想：分而治之
    //（3）快排可能存在最坏情况，需要把枢轴值选取得尽量随机化来缓解最坏情况下的时间复杂度
    //（4）最好情况就是分区每次都很均匀，递归深度就是logN，每次分区操作需要N，所以最好O(NlogN)，最坏情况就是分区极不平衡，一边0一边剩余所有，这种递归深度就是N

    /**
     * 快速排序
     * @param arr 待排序数组
     */
    public static void quickSort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    /**
     * 快速排序递归实现
     * @param arr 待排序数组
     * @param begin 待排序范围的起始索引（包含）
     * @param end 待排序范围的结束索引（包含）
     */
    private static void quickSort(int[] arr, int begin, int end) {
        // 递归结束条件：当前范围数组内只有一个元素，这里用大于等于，想象两个元素分区后的情况
        if (begin >= end){
            return;
        }
        // 递的时候将基准点元素放到合适位置并且把比基准点小的元素放基准点元素左边，比基准点大或等的元素放基准点元素右边
        int pivot = partition(arr, begin, end);
        // 再对基准点左边的区域和右边的区域进行快速排序
        quickSort(arr, begin, pivot - 1);
        quickSort(arr, pivot + 1, end);
    }

    /**
     * 洛穆托分区思想进行分区操作
     * @param arr 待分区数组
     * @param begin 待分区范围的起始索引（包含）
     * @param end 待分区范围的结束索引（包含）
     * @return 分区好后的基准点元素索引
     */
    private static int partition(int[] arr, int begin, int end){
        int lt = begin; // lt指针负责找到小于基准点的元素
        int ge = begin; // ge指针负责找到大于等于基准点的元素
        int index = ThreadLocalRandom.current().nextInt(end - begin + 1) + begin; // 随机数优化
        swap(arr, index, begin);
        int pivot = arr[end]; // 基准点元素
        while (lt < end){ // lt指针在end之前的范围内找比end的元素小的元素
            if (arr[lt] < pivot){ // lt找到比基准点小的元素
                if (lt != ge){ // 并且ge找到比基准点大或等的元素，那么交换，如果lt和ge不相等，说明ge肯定等待了，那么ge肯定找到了比基准点大或等的元素
                    swap(arr, lt, ge);
                }
                ge++; // ge自增一，ge的下一个元素肯定是比基准点大或等的元素，因为要么lt就是ge + 1，交换后ge+1就是比基准点大或等的元素，要么lt在ge很后面，那么lt和ge之间的全是大于基准点的元素，那么ge+1就是比基准点大或等的元素，ge+1肯定满足条件；要么lt和ge相等，这个时候ge还没有找到比基准点大或等的元素，那么ge+1就是比基准点大或等的元素，ge+1表示继续找找比基准点大或等的元素，一旦找到了，ge指向的就是大于等于基准点的第一个元素
            }
            lt++; // lt自增一
        }
        swap(arr, ge, end); // 将基准点与ge交换，让基准点元素放到合适的位置
        return ge;
    }

    /**
     * 交换两个元素
     * @param arr 数组
     * @param index1 索引1
     * @param index2 索引2
     */
    private static void swap(int[] arr, int index1, int index2) {
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
}
